1. Field of the Invention
The present invention relates to an encoding apparatus for generating and puncturing an error correcting code, to a decoding apparatus for using the punctured error correcting code to correct erroneous data, and to an encoding and decoding system including the encoding apparatus and the decoding apparatus.
2. Description of the Related Art
Encoding and decoding systems are used for video and other image processing. It is sometimes desirable to reduce the computational load on the encoding apparatus, even if the computational load on the decoding apparatus increases. Distributed source coding (DSC), in which the encoding apparatus encodes information from multiple correlated information sources separately and the decoding apparatus decodes the separately encoded data jointly, is a known way to shift the main burden of the computations from the encoding apparatus to the decoding apparatus.
Distributed source coding relies on two theorems. The Slepian-Wolf theorem gives the admissible compression rate region, that is, the set of compression rates that permit the separately encoded data from the multiple information sources to be decoded without distortion. The Wyner-Ziv theorem gives a rate distortion function that applies when distortion occurs at one of the information sources. The compression limit for sources encoded separately, without cross-observation, in the range of the conditions given by the Slepian-Wolf and Wyner-Ziv theorems is known to be the same as the compression limit for the same sources encoded with cross-observation.
A conventional DSC encoding and decoding system 51 including an encoding apparatus 60, a decoding apparatus 70, and a puncturing table storage unit 80 is shown in FIG. 1.
The encoding apparatus 60 sequentially generates an error correcting code Ecc1 from externally input data S1 received from an information source as a string of information bits. The error correcting code Ecc1 is punctured by deleting some of its bits. The remaining code bits, constituting a punctured error correcting code Ecc2, are transmitted to the decoding apparatus 70. The number of bits deleted varies depending on the transmission rate R.
The decoding apparatus 70 uses the punctured error correcting code Ecc2 to correct erroneous data E received from another information source, thereby generating decoded data S2. The erroneous data E may be referred to as side information. In the context of signal processing theory, the side information is similar to data received through a noisy channel. In the context of distributed video coding (DVC), the side information is locally predicted image data.
The puncturing table storage unit 80 stores a puncturing table T that defines puncturing patterns P corresponding to different transmission rates R.
The encoding apparatus 60 includes an encoder 61, a puncturing pattern selector 62, and a puncturing unit 63.
The encoder 61 generates the error correcting code Ecc1 from the externally input information S1 and outputs the error correcting code Ecc1 to the puncturing unit 63.
The puncturing pattern selector 62 selects a puncturing pattern P corresponding to the transmission rate R from the puncturing table T and outputs the puncturing pattern P to the puncturing unit 63. This operation is substantially concurrent with the operation of the encoder 61.
The puncturing unit 63 punctures the error correcting code Ecc1 by deleting bits indicated in the puncturing pattern P, thereby generating the punctured error correcting code Ecc2.
The decoding apparatus 70 includes a decoder 71, which corrects the erroneous data E according to the transmission rate R and punctured error correcting code Ecc2 to generate the decoded data S2.
An exemplary puncturing table T is illustrated as a matrix in FIG. 2. Each horizontal row vector in FIG. 2 represents a puncturing pattern P that is applied to each eight-bit octet of the error correcting code Ecc1. When the transmission rate is R bits per octet, the puncturing pattern selector 62 selects the (R+1)-th row vector. For example, when the transmission rate is three bits per octet, the puncturing unit 63 refers to the fourth row vector.
The puncturing unit 63 deletes the bits in positions corresponding to 0's in the selected puncturing pattern P from the error correcting code Ecc1 generated by the encoder 61, and outputs the bits in positions corresponding to 1's as the punctured error code Ecc2. If the value of the x-th bit of the puncturing pattern P in the (R+1)-th row is denoted T(R+1, x), then the puncturing unit 63 removes the x-th bit of each octet of the error correcting code bit Ecc1 if T(R+1, x)=0, and outputs the x-th bit of each octet if T(R+1, x)=1. The puncturing process thus involves a repeated conditional branching step in which the puncturing unit 63 tests the value of T(R+1, x) to decide what to do with the x-th bit.
The error correcting code used in the encoding and decoding system 51 may be, for example, a low density parity check accumulate code (LDPCA code) or a sum LDPCA code (SLDPCA code) as disclosed by Varodayan et al. in ‘Rate-Adaptive Distributed Source Coding Using Low-Density Parity-Check Codes’ in Proc. Asilomar Conference on Signals, Systems, and Computers, 2005, Pacific Grove, Calif., November 2005. An LDPCA code is generated by accumulating an LDPC code before the puncturing process is carried out. SLDPCA codes are obtained by summing LDPCA codes. Varodayan et al. show that the transmission rate (Mbits/s) of an LDPCA or SLDPCA code can be changed flexibly because, unlike non-accumulated LDPC codes, LDPCA and SLDPCA codes can maintain high decoding performance even when punctured. Turbo codes also have this feature. Transmission rate-flexibility enhances the general usefulness of an encoding and decoding system.
Irregular repeat-accumulate (IRA) codes, which combine iterative codes with interleavers and accumulators, provide high decoding performance, but with less flexibility.
In the conventional encoding and decoding system 51 described above, the puncturing process involves the following computational loads (1) to (3).
(1) Selection of a puncturing pattern P corresponding to the transmission rate R.
(2) Reference to the puncturing pattern P during the puncturing process.
(3) Execution of a separate conditional branching process for each bit of error correcting code Ecc1.
The third of these computational loads increases with the number of Ecc1 bits, and thus with the length of the information bit string. In a distributed video coding system, for example, in which the information bit string may be very long, this becomes a significant obstacle to the goal of lowering the computational load on the encoder.